package unionfindset;

import java.util.Arrays;

public class UnionFindSet {

    // 底层是一个数组
    private int[] elem;

    public UnionFindSet(int n) {
        this.elem = new int[n];
        // 整体初始化为 -1, 代表根
        Arrays.fill(elem, -1);
    }

    /**
     * 查找x的根
     *
     * @param x
     * @return
     */
    public int findRoot(int x) {
        if (x < 0) {
            throw new IndexOutOfBoundsException("数据不合法");
        }
        while (elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }

    /**
     * 合并x1和x2，但是有个问题，x1和x2必须都是根
     * 所以，先得查找x1和x2的根
     *
     * @param x1 1
     * @param x2 0
     */
    public void union(int x1, int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if (index1 == index2) {
            // 说明 x1和x2 根是相同的, 不进行合并
            return;
        }
        elem[index1] = elem[index1] + elem[index2];
        elem[index2] = index1;
    }

    /**
     * 判断两个数字 是不是在同一个集合当中
     *
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameSet(int x1, int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if (index1 == index2) {
            // 说明 x1和x2 根是相同的  在同一个集合
            return true;
        }
        return false;
    }

    /**
     * 求数组当中集合的个数
     *
     * @return
     */
    public int getCount() {
        int count = 0;
        for (int x : elem) {
            if (x < 0) {
                count++;
            }
        }
        return count;
    }

    public void printArr() {
        for (int i = 0; i < elem.length; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }
}
